//Given a string s, return the longest palindromic substring in s. 
//
// 
// Example 1: 
//
// 
//Input: s = "babad"
//Output: "bab"
//Note: "aba" is also a valid answer.
// 
//
// Example 2: 
//
// 
//Input: s = "cbbd"
//Output: "bb"
// 
//
// Example 3: 
//
// 
//Input: s = "a"
//Output: "a"
// 
//
// Example 4: 
//
// 
//Input: s = "ac"
//Output: "a"
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 1000 
// s consist of only digits and English letters (lower-case and/or upper-case), 
//
// Related Topics 字符串 动态规划 
// 👍 3632 👎 0


package leetcode.editor.cn;

//Java：Longest Palindromic Substring
class P5LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new P5LongestPalindromicSubstring().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            if(s==null||s.length()==0){
                return null;
            }
            if (s.length() < 2) { // 单个字符肯定是回文串，直接返回s
                return s;
            }
            boolean[][] dp = new boolean[s.length()][s.length()];  // 初始化一个二维数组，值默认是false
            String result = s.substring(0, 1);
            for (int j = 0; j < s.length(); j++) {
                for (int i = 0; i <= j; i++) {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1]);
                    if (dp[i][j]) {
                        if (j - i + 1 > result.length()) {
                            result = s.substring(i, j + 1);
                        }
                    }
                }
            }
            return result;
        }


        boolean isValid(String str, int left, int right) {
            char[] array = str.toCharArray();
            while (left < right && array[left] == array[right]) {
                left++;
                right--;
            }
            if (left >= right) {
                return true;
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}